package main

import "fmt"

// 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
// 示例 1：
// 输入：s = "3[a]2[bc]"
// 输出："aaabcbc"
// 示例 2：
// 输入：s = "3[a2[c]]"
// 输出："accaccacc"

// 栈；先重复最里层的

func decodeString(s string) string {
	sk := []byte{}
	for i := 0; i < len(s); i++ {
		if s[i] != ']' {
			sk = append(sk, s[i])
		} else {
			// 弹出，遇到[
			subStr := []byte{}
			for len(sk) > 0 && sk[len(sk)-1] != '[' {
				subStr = append(subStr, sk[len(sk)-1])
				sk = sk[:len(sk)-1]
			}
			// 去掉[
			sk = sk[:len(sk)-1]
			// 判断重复次数   如100
			num := []byte{}
			for len(sk) > 0 && sk[len(sk)-1] >= '0' && sk[len(sk)-1] <= '9' {
				num = append(num, sk[len(sk)-1])
				sk = sk[:len(sk)-1]
			}
			cnt := 0
			for j := len(num) - 1; j >= 0; j-- {
				cnt = cnt*10 + int(num[j]-'0')
			}
			// 重复  substr的逆序
			n := len(subStr)
			for j := 0; j < n/2; j++ {
				subStr[j], subStr[n-j-1] = subStr[n-j-1], subStr[j]
			}
			for cnt > 0 {
				sk = append(sk, subStr...)
				cnt--
			}
		}
	}

	return string(sk)
}

func main() {
	type inAndOut struct {
		input  string
		output string
	}
	cases := []inAndOut{
		{"3[a]2[bc]", "aaabcbc"},
		{"3[a2[c]]", "accaccacc"},
		{"2[abc]3[cd]ef", "abcabccdcdcdef"},
	}
	for _, param := range cases {
		res := decodeString(param.input)
		if res != param.output {
			fmt.Printf("FAIL input:%v   output:%v\n", param.input, res)
		} else {
			fmt.Println("PASS")
		}
	}

}
